package LeetCode.Leet100_199.Leet120_129.Leet121;

/**
 * @ClassName Solution_3
 * @Author 孙天赐
 * @Date 2025/10/28 8:43
 * @Description TODO: 方法三   动态规划（我自己写的） 3ms 21.15%
 */
class Solution_3 {
    public int maxProfit(int[] prices) {
        if (prices.length == 1) {
            return 0;
        }
        int max = 0;
        // dp[i] 表示第i天卖出，所能得到的最大利润（不管第几天买入）
        int[] dp = new int[prices.length];
        dp[0] = 0;
        for (int i = 1; i < dp.length; i++) {
            // 计算第i天卖出的最大利润
            dp[i] = dp[i - 1] + (prices[i] - prices[i - 1]);
            // 如果无利润，设置为0
            if (dp[i] < 0) {
                dp[i] = 0;
            }
            // 更新全局最大值
            if (dp[i] > max) {
                max = dp[i];
            }
        }
        return max;
    }
}
